package com.cyy.heap;

import com.cyy.printer.BinaryTreeInfo;

import java.util.Comparator;

/**
 * 二叉堆 - > 大顶堆
 * 使用数组实现二叉堆
 * @author 会玩的洋洋
 * @since 2022-03-01
 * @param <E>
 */
public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo {
    /**
     * 存储元素的数组
     */
    private E[] elements;

    /**
     * 默认大小为 10
     */
    private static final int DEFAULT_CAPACITY = 10;

    public BinaryHeap(E[] elements, Comparator<E> comparator) {
        super(comparator);
        if (elements == null || elements.length == 0) {
            this.elements = (E[])new Object[DEFAULT_CAPACITY];
        } else {
            size = elements.length;
            int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
            this.elements = (E[])new Object[capacity];
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
        }
        heapify();
    }

    public BinaryHeap(E[] elements) {
        this(elements, null);
    }

    public BinaryHeap() {
        this(null ,null);
    }

    public BinaryHeap(Comparator<E> comparator) {
        super(comparator);
        this.elements = (E[])new Object[DEFAULT_CAPACITY];
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        // 考虑扩容
        ensureCapacity(size + 1);
        elements[size++] = element;
        // 直接 siftUp，进行从上到下的上滤操作
        siftUp(size - 1);
    }

    @Override
    public E get() {
        emptyCheck();
        return elements[0];
    }

    @Override
    public E remove() {
        emptyCheck();

        int lastIndex = --size;
        E root = elements[0];
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;

        siftDown(0);
        return root;
    }

    @Override
    public E replace(E element) {
        elementNotNullCheck(element);
        E root = null;
        if (size == 0) {
            elements[0] = element;
            size++;
        } else {
            root = elements[0];
            elements[0] = element;
            siftDown(0);
        }
        return root;
    }

    /**
     * 判断二叉堆是否为空
     */
    private void emptyCheck() {
        if (size == 0) {
            throw new IllegalArgumentException("Heap is Empty!!");
        }
    }

    /**
     * 检查元素是否为空
     * @param element 待检查元素
     */
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be empty!!");
        }
    }

    /**
     * 扩容操作  每次扩容至原来的 1.5 倍
     * @param capacity 当前的容量
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (capacity <= oldCapacity) {
            return;
        }

        // 如果数组范围超出原数组，则扩容原来的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        Object[] newElements = new Object[newCapacity];
        for(int i = 0 ; i < size ; ++i) {
            newElements[i] = elements[i];
        }
        elements = (E[])newElements;
    }

    /**
     * 上滤操作
     * @param index 需要上滤的索引
     */
    private void siftUp(int index) {
        E element = elements[index];
        while (index > 0) {
            int pindex = (index - 1) >> 1;
            E parent = elements[pindex];
            if (compare(element, parent) <= 0) {
                break;
            }
            // 将父元素存储到index的位置
            elements[index] = parent;
            // 重新赋值 index
            index = pindex;
        }
        elements[index] = element;
    }

    /**
     * 下滤操作
     * @param index 需要下滤的索引
     */
    private void siftDown(int index) {
        E element = elements[index];
        int half = size >> 1;
        // 第一个叶子节点的索引 == 非叶子节点的数量
        // index < 第一个叶子节点的索引
        // 必须保证 index 是非叶子节点
        while (index < half) {
            /*
                index的节点有两种
                1、只有左子节点
                2、既有左子节点，又有右子节点
                默认使用左子节点比较
             */
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];

            // 右子树情况
            int rightIndex = childIndex + 1;
            if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
                child = elements[childIndex = rightIndex];
            }

            if (compare(element, child) >= 0) {
                break;
            }

            // 将大的值赋值给原来元素，并将下标移动
            elements[index] = child;
            index = childIndex;
        }
        elements[index] = element;
    }

    /**
     * 批量建堆
     * 自下而上的下滤
     */
    private void heapify() {
        // 自下而上的下滤
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    @Override
    public Object root() {
        return 0;
    }

    @Override
    public Object left(Object node) {
        Integer index = (Integer) node;
        index = (index << 1) + 1;
        return index >= size ? null : index;
    }

    @Override
    public Object right(Object node) {
        Integer index = (Integer) node;
        index = (index << 1) + 2;
        return index >= size ? null : index;
    }

    @Override
    public Object string(Object node) {
        Integer index = (Integer) node;
        return elements[index];
    }
}
